#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
#include <functional>
#include <assert.h>
#include <iostream>
using namespace std;
template <typename K, typename V>
struct ListNode {
	ListNode() :key(0), val(0), next(nullptr) {
	
	}
	ListNode(K key, V val) :key(key), val(val), next(nullptr) {
	
	}
	K key;
	V val;
	ListNode<K, V>* next;
};
template <typename K, typename V>
class HashTable {
public:
	using hash_t = std::hash<K>;
	HashTable() :capacity(64), size(0), map(nullptr) {
		mallocHashTable();
	}
	HashTable(HashTable& other) {
		if (this != &other) {
			capacity = other.capacity;
			mallocHashTable();
			insertTomap(capacity, other.map);
		}	
	}
	HashTable(HashTable&& other) :capacity(std::forward<size_t>(other.capacity)), size(std::forward<size_t>(other.size)), map(std::forward<ListNode<K, V>**>(other.map)) {
		other.capacity = 0;
		other.size = 0;
		other.map = nullptr;
	}
	HashTable& operator = (HashTable& other) {
		if (this != &other) {
			capacity = other.capacity;
			mallocHashTable();
			insertTomap(capacity, other.map);
		}
		return *this;
	}
	V& operator[](K &key) {
		ListNode<K, V>* findnode = search(key);
		assert(findnode);
		return findnode->val;
	}
	V& operator[](K&& key) {
		ListNode<K, V>* findnode = search(key);
		assert(findnode);
		return findnode->val;
	}
	~HashTable() {
		destoryHashTable();
	}
public:
	void insert(K &key, V &val) {
		if (size >= capacity) {
			remallocHashTable();
		}
		if (find(key, val)) {
			return;
		}
		insertToHead(key, val);
		size++;
	}
	void insert(K&& key, V&& val) {
		if (size >= capacity) {
			remallocHashTable();
		}
		if (find(key, val)) {
			return;
		}
		insertToHead(key, val);
		size++;
	}

	void remove(K& key) {
		removeListNode(key);
	}
	
	void remove(K&& key) {
		removeListNode(key);
	}

	bool count(K& key) {
		return search(key) == nullptr ? false : true;
	}
	bool count(K&& key) {
		return search(key) == nullptr ? false : true;
	}
	
	size_t count() {
		return size;
	}
private:
	
	void mallocHashTable() {
		map = new ListNode<K, V>* [capacity];
		for (int i = 0; i < capacity; ++i) {
			map[i] = nullptr;
		}
	}
	
	void remallocHashTable() {
		capacity = capacity << 1;
		ListNode<K, V>** s_map = map;
		std::fill(map, map + capacity, nullptr);
		size = 0;
		size_t precapacity = capacity >> 1;
		insertTomap(precapacity, s_map);
		delete[]s_map;
		s_map = nullptr;
	}
	
	void insertTomap(size_t& capacity, ListNode<K, V> **map) {
		size = 0;
		{
			for (int i = 0; i < capacity; ++i) {
				ListNode<K, V>* head = map[i];
				insertListNodeTomap(head);
			}
		}
	}
	
	size_t getIndex(K &key) {
		hash_t hash;
		auto code = hash(key);
		code = code ^ (code >> 16);
		return code & (capacity - 1);

	}
	
	bool find(K &key, V &val = 0) {
		auto index = getIndex(key);
		if (!map[index]) {
			return false;
		}
		return findListNode(map[index], key, val);
	}
	
	bool findListNode(ListNode<K, V>*head, K &key, V &val) {
		if (!head) {
			return false;
		}
		if (head->key == key) {
			head->val = val;
			return true;
		}
		return findListNode(head->next, key, val);
	}
	
	ListNode<K, V>* search(K& key) {
		size_t index = getIndex(key);
		if (!map[index]) {
			return nullptr;
		}
		return searchListNode(map[index], key);
	}
	
	ListNode<K, V>* searchListNode(ListNode<K, V>* head, K &key) {
		if (!head) {
			return nullptr;
		}
		if (head->key == key) {
			return head;
		}
		return searchListNode(head->next, key);

	}
	
	void insertToHead(K &key, V &val) {
		size_t index = getIndex(key);
		ListNode<K, V>* head = map[index];
		ListNode<K, V>* node = nullptr;
		node = new ListNode<K, V>(key, val);
		if (!head) {
			map[index] = node;
			return;
		}
		 
		node->next = head;
		map[index] = node;
	}
	
	void insertListNodeTomap(ListNode<K, V>* head) {
		if (!head) {
			return;
		}
		insert(head->key, head->val);
		insertListNodeTomap(head->next);
	}
	
	bool removeListNode(K &key) {
		if (!search(key)) {
			return false;
		}
		size_t index = getIndex(key);
		return removeListNode(index, key);
	}
	
	bool removeListNode(size_t &index, K& key) {
		ListNode<K, V>* head = map[index];
		ListNode<K, V>* pre = head, * p = head->next;
		if (pre->key == key) {
			delete pre;
			pre = nullptr;
			map[index] = p;
			size--;
			return true;
		}
		else {
			while (p) {
				if (p->key == key) {
					pre->next = p->next;
					delete p;
					p = nullptr;
					size--;
					return true;
				}
				pre = p; 
				p = p->next;
			}
		}
		return false;
	}
	
	void destoryListNode(ListNode<K, V>* head) {
		if (!head) {
			return;
		}
		ListNode<K, V>* delnode = head;
		head = head->next;
		if (delnode) {
			delete delnode;
			delnode = nullptr;
		}
		size--;
		destoryListNode(head);
	}
	void destoryHashTable() {
		for (int i = 0; i < capacity; ++i) {
			destoryListNode(map[i]);
		}
	}
	
private:
	ListNode<K, V>** map;
	size_t size;
	size_t capacity;
};
#endif // !_HASH_TABLE

